package org.guass.linklist;

/**
 * @author guass
 * @date 2022年03月11日 17:33
 */
public class LinkList<T> {

    protected LinkNode first;

    protected int maxSize = 100;

    protected int currentSize;

    public LinkList(){
    }

    public LinkList(T data){
        first = new LinkNode<T>(data);
    }

    public LinkList(T data, int maxSize){
        first = new LinkNode<T>(data);
        this.maxSize = maxSize;
    }

    /**
     * 将链表置为空表
     */
    public void makeEmpty(){
        first = null;
        currentSize = 0;
    }

    /**
     * 获取链表的长度
     * @return
     */
    public int getLength(){
        return currentSize;
    }

    public void print(){
        LinkNode<T> p = first;
        String ss = "";
        while (p != null){
            ss += p.getData() + "->";
            p = p.nextNode;
        }
        System.out.println("ss = " + ss + "null");
    }

    public int getLength2(){
        LinkNode<T> p = first;
        int ss = 0;
        while (p != null){
            p = p.nextNode;
            ss++;
        }
        return ss;
    }


    public LinkNode<T> getFirst() {
        return first;
    }

    public void setFirst(LinkNode<T> first) {
        this.first = first;
    }

    /**
     * 搜索包含数据x的节点
     * @param x
     * @return
     */
    public LinkNode<T> search(T x){
        LinkNode p  = first;
        while (p != null){
            if (p.getData().equals(x)) {
                return p;
            }
            p = p.nextNode;
        }
        return null;
    }

    /**
     * 搜索第i个元素的地址
     * @param i
     * @return
     */
    public LinkNode<T> locate(int i){

        if (i < 0 || i > currentSize) {
            throw new RuntimeException("err params !!");
        }

        LinkNode p = first;

        int k = 0;
        while (p != null && k < i) {
            p = p.nextNode;
            k++;
        }
        return p;
    }

    /**
     * 取出第i个元素的值
     * @param i
     * @return
     */
    public T getData(int i){
        return locate(i).getData();
    }

    /**
     * 用x修改第i个元素的值
     * @param x
     * @param i
     */
    public void setData(T x, int i){
        locate(i).setData(x);
    }


    /**
     * 将新元素插入到第i个节点之后,i从1开始, i=0 表示插入到第一个节点之前
     * @param i
     * @param x
     * @return
     */
    public boolean insert(int i, T x){

        if(i < 0 || i > currentSize){
            throw new RuntimeException("errr");
        }

        // TODO: 2022/3/11  表示插入到第一个节点之前
        LinkNode<T> newNode = new LinkNode<T>(x);
        if (i == 0) {

            if (first == null) {
                first = newNode;
            }else {
                newNode.nextNode = first;
                first = newNode;
            }
        }else if( i > 0 && i < currentSize){
            // TODO: 2022/3/11 插入中间
            LinkNode<T> currentNode = first;
            for (int j = 0; j < i - 1; j++) {
                currentNode = currentNode.nextNode;
            }
            newNode.nextNode = currentNode.nextNode;
            currentNode.nextNode = newNode;
        }else {
            // TODO: 2022/3/11 插入结尾
            LinkNode<T> lastNode = getLastNode();
            lastNode.nextNode = newNode;
        }
        currentSize++;
        return true;
    }

    /**
     * 获取最后一个元素
     * @return
     */
    public LinkNode<T> getLastNode(){
        LinkNode<T> currentNode = first;
        for (int j = 0; j < currentSize - 1; j++) {
            currentNode = currentNode.nextNode;
        }
        return currentNode;
    }

    /**
     * 删除第i个元素并返回
     * @param i(i >= 1  i<= currentSize)
     * @return
     */
    public boolean remove(int i){

        if (i < 1 || i > currentSize){
            throw  new RuntimeException("err params!!!");
        }

        LinkNode<T> currentNode = locate(i);
        LinkNode<T> preNode;

        if( i == 1){
            first = currentNode;
        }else if(i < currentSize){
            preNode = locate(i - 1 - 1);
            preNode.nextNode = currentNode;
        }else {
            LinkNode<T> node = locate(i - 2);
            node.nextNode = null;

        }

        return true;
    }

    public boolean remove2(int i){
        return false;
    }

    /**
     * 链表为空
     * @return
     */
    public boolean isEmpty(){
        return first.nextNode == null;
    }


    public boolean isFull(){
        return currentSize == maxSize;
    }
}
